import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

public class Demo {
    public static void main(String[] args) {
//        System.out.println(sss("1"));

        TreeNode treeNode = new TreeNode(1, new TreeNode(2, null, new TreeNode(5, null, null)), new TreeNode(3, null, null));

        List<Integer> data = nodeTree(treeNode);
        for (Integer item:data){
            System.out.println(item);
        }
    }

    public static String sss(String n){
        int size = n.length();
        if (size % 2 == 0){
            int num = size / 2;
            String end = "";
            char[] arr = n.toCharArray();
            for (int i = num - 1; i >= 0; i--){
                end += arr[i];
            }

            String start = n.substring(0, num);
            System.out.println(start + "    " + end);
            return start + end;
        }

        if (size % 2 == 1){
            int num = size / 2;
            if (num > 0){
                String end = "";
                char[] arr = n.toCharArray();
                for (int i = num - 1; i >= 0; i--){
                    end += arr[i];
                }

                String start = n.substring(0, num + 1);
                System.out.println(start + "    " + end);
                return start + end;
            }else{
                return n;
            }
        }
        return null;
    }

    static class Node{
        public int index;
        public char item;
        public Node(int index, char item ){
            this.index = index;
            this.item = item;
        }

        @Override
        public boolean equals(Object obj) {
            Node character = (Node) obj;
            if (item == character.item){
                return true;
            }

            return false;
        }
    }

    public static int ll(String s){
        if(s != null && s.length() > 0){
            char[] arr = s.toCharArray();
//            int startIndex = 0;
            int endIndex = 0;
            int max = 1;
            ArrayList<Node> list = new ArrayList<>();
            while(endIndex < s.length()){
                char item = arr[endIndex];
                Node node = new Node(endIndex, item);
                int indexOf = list.indexOf(node);
                if (indexOf == -1){
                    list.add(node);
                }else{
                    max = Math.max(list.size(), max);

//                    startIndex = list.get(indexOf).index + 1;

                    for (int i = indexOf; i >=0; i--){
                        list.remove(i);
                    }
                    list.add(node);
                }
                endIndex++;

            }
            max = Math.max(list.size(), max);
            return max;
        }

        return 0;
    }

    static class  TreeNode{
        public int value;
        public TreeNode left;
        public TreeNode right;

        public TreeNode(int value, TreeNode left, TreeNode right){
            this.value = value;
            this.left = left;
            this.right = right;
        }
    }

    public static Stack<TreeNode> rightNodeStack = new Stack<>();

    /**
     * 算法程序入口
     * @param root
     * @return
     */
    public static List<Integer> nodeTree(TreeNode root){
        List<Integer> rightNodes = new ArrayList<>();

        List<TreeNode> levelNodes = new ArrayList<>();
        if (root.left != null){
            levelNodes.add(root.left);
        }

        if (root.right != null){
            levelNodes.add(root.right);
        }

        handleNode(levelNodes);
        rightNodeStack.push(root);

        while (!rightNodeStack.isEmpty()){
            rightNodes.add(rightNodeStack.pop().value);
        }
        return rightNodes;
    }

    public static TreeNode handleNode(List<TreeNode> levelNodes){
        List<TreeNode> levelChildNodes = new ArrayList<>();

        for (TreeNode item: levelNodes){
            if (item.left != null){
                levelChildNodes.add(item.left);
            }

            if (item.right != null){
                levelChildNodes.add(item.right);
            }
        }

        if (levelChildNodes.size() == 0){
            rightNodeStack.push(levelNodes.get(levelNodes.size() - 1));
            return levelNodes.get(levelNodes.size() - 1);
        }else {
            TreeNode childNode = handleNode(levelChildNodes);
            for (TreeNode parentNode: levelNodes){
                if (parentNode.left == childNode || parentNode.right == childNode){
                    rightNodeStack.push(parentNode);
                    return parentNode;
                }
            }

            return null;
        }
    }
}
